//
// Created by 123 on 2024/3/23.
//
/**
 * 思想：从某一个顶点开始构建，
 * 每次将代价最小的新顶点纳入生成树，
 * 直到所有顶点都纳入为止
 */
#include <iostream>
#include <vector>
#include "../../6_树/并查集/union_look_up_set.cpp"

using namespace std;
#define VexNum 6

int grap[VexNum][VexNum] = {
        {99999, 6,     1,     5,     99999, 99999,},
        {6,     99999, 5,     99999, 3,     99999,},
        {1,     5,     99999, 5,     6,     4,},
        {5,     99999, 5,     99999, 99999, 2,},
        {99999, 3,     6,     99999, 99999, 6,},
        {99999, 99999, 4,     2,     6,     99999,},
};
string vex[VexNum] = {"V1", "V2", "V3", "V4", "V5", "V6"};
//bool isVisited[VexNum] = {false, false, false, false, false, false};

vector<string> prim(string v) {
    int v_index = -1;
    for (int i = 0; i < VexNum; ++i) {
        if (vex[i] == v)
            v_index = i;
    }
    vector<int> arr;
    arr.push_back(v_index);
    int b_node = v_index;
    vector<string> str;
    while (arr.size() < VexNum) {
        int min_index = -1;
        int min_num = 9999;
        for (int i = 0; i < arr.size(); ++i) {
            for (int j = 0; j < VexNum; ++j) {
                if (min_num > grap[arr[i]][j] && !isSameSet(v_index, j)) {
                    b_node = arr[i];
                    min_num = grap[arr[i]][j];
                    min_index = j;
                }
            }
        }
        unionNode(v_index, min_index);
        arr.push_back(min_index);
        str.push_back(vex[b_node] + "--->" + vex[min_index]);
    }
    return str;
}

int main() {
    initUnLoSet();
    add(0);
    add(1);
    add(2);
    add(3);
    add(4);
    add(5);
    vector<string> arr = prim("V3");
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << "       ";
    }


}





